package com.mashibing.class07;

import java.util.ArrayList;
import java.util.List;

//letcode113 : https://leetcode.com/problems/path-sum-ii
public class Code04_PathSumII {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        ArrayList<Integer> path = new ArrayList<>();
        process(root, path, 0, sum, ans);
        return ans;
    }

    /**
     * @param treeNode     当前节点
     * @param path         之前节点保留那些值 (路径)
     * @param preSum       之前节点的值的和.
     * @param sum          符合条件的路径和的值
     * @param ans          存储符合条件的路径.
     */
    public static void process(TreeNode treeNode, List<Integer> path,
                               int preSum, int sum, List<List<Integer>> ans) {
        // 当前节点为叶子结点
        if (treeNode.left==null&&treeNode.right==null){
            if (preSum+treeNode.val==sum){
                path.add(treeNode.val);
                for (Integer num : path) {
                    path.add(treeNode.val);
                    ans.add(copy(path));
                    path.remove(path.size()-1);
                }
                return;
            }
        }
        // 当前节点是非叶子节点
        path.add(treeNode.val);
        preSum += treeNode.val;
        if (treeNode.left!=null){
            process(treeNode.left,path,preSum,sum,ans);
        }
        if (treeNode.right!=null){
            process(treeNode.right,path,preSum,sum,ans);
        }
        path.remove(path.size()-1);
    }
    public static List<Integer> copy(List<Integer> path){
        List<Integer> ans = new ArrayList<>();
        for (Integer num : path) {
            ans.add(num);
        }
        return ans;
    }
}
